package javaStudy;

/**
 * Created by qq65827 on 2015/2/5.
 */
public class BinarySearch {

    public static int binarySearch(int[] src, int i) {
        int length = src.length;
        //return binarySearch0(src, 0, length, i);
        return binarySearch1(src, 0, length, i);
    }

    public static int binarySearch0(int[] src, int fromIndex, int toIndex, int key) {
        int low = fromIndex;
        int high = toIndex;

        while (low < high) {
            int mid = (low + high) >>> 1;
            int midValue = src[mid];

            if (midValue < key) {   //说明在右边
                low = mid + 1;
            } else if (midValue > key) {
                high = mid - 1;
            } else {
                return mid;  //找到
            }
        }
        return -(low + 1);
    }

    public static int binarySearch1(int[] src, int fromIndex, int toIndex, int key) {
        int low = fromIndex;
        int high = toIndex;

        while (low < high) {
            int mid = (low + high) >>> 1;
            int midValue = src[mid];
            if (midValue > key) {  //说明在左侧
                high = mid - 1;
            } else if (midValue < key) {
                low = mid + 1;
            } else {
                return mid;
            }
        }
        return -(low + 1);
    }

}
